今天一樣再來介紹一個排序，叫做插入排序法(Insert Sort)．不知道昨天介紹完泡沫排序之後，大家在電路的部分對排序法有沒有更多的想法，今天來談談如何做出跟想像中不一樣的插入排序，首先一樣先來看一下插入排序的Pseudocode

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

當要插入一個新的元素時，就要去找到適合自己的位置，如果換成用電路做的話該怎麼去平行化呢？

首先，假設有n個元素，就創一組n+1個的bit array跟放n個元素的register array，

用一個例子說明，假設原本就放了排序好的四個元素，這時候要插入一個4，bitarray會從1開始更新到n，比原本array的值還大就填1，小於等於填0，bitarray最左邊永遠填1，

接下來開始找2’b10的位置，像上圖標記為綠色的地方，然後把四插入進去，剩下的往後面娜一個位置，接下在插入0的數字，一樣先更新bit array的值，然後找出2’b10的位置，把值插進去，剩下的值往後挪，如下圖．

最後就完成拉！！

看到這裡應該就可以開始動手做做看囉．

Insert sort Verilog code：

reg [6:0]bit_array;
reg [2:0]insert_array[5:0];

always@(*)begin
  if(rst)begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = 0;
  bit_array[6] = 1;
end
else if(in_valid)begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = (data_in > insert_array[i]) ? 1 : 0;		  
end
else begin
  for(i=0;i<6;i=i+1)
    bit_array[i] = 0;
  bit_array[6] = 1;
end
end

always@(posedge clk)begin
  if(in_valid)begin
  for(i=6;i>1;i=i-1)begin
    insert_array[i-1] <= (bit_array[i-:2]==2'b10) ? data_in : 
								 (bit_array[i-:2]==2'b11) ? insert_array[i-1] : insert_array[i];		
  end
end
end 

always@(posedge clk)begin
  if(in_valid)
  out_valid <= 1;
else
  out_valid <= 0;
end

跑模擬時，我把全部array設為最大值，insert順序為1 5 3 6 4 0，模擬結果可以參考上圖．